In applications such as image or video libraries, it is desirable to have an efficient representation and storage of the outline or shape of objects or parts of objects appearing in still or video images. A known technique for shape-based indexing and retrieval uses Curvature Scale Space (CSS) representation. Details of the CSS representation can be found in the papers “Robust and Efficient Shape Indexing through Curvature Scale Space” Proc. British Machine Vision conference, pp 53-63, Edinburgh, UK, 1996 and “Indexing an Image Database by Shape Content using Curvature Scale Space” Proc. IEE Colloquium on Intelligent Databases, London 1996, both by F. Mokhtarian, S. Abbasi and J. Kittler, the contents of which are incorporated herein by reference.
The CSS representation uses a curvature function for the outline of the object, starting from an arbitrary point on the outline. The curvature function is studied as the outline shape is evolved by a series of deformations which smooth the shape. More specifically, the zero crossings of the derivative of the curvature function convolved with a family of Gaussian filters are computed. The zero crossings are plotted on a graph, known as the Curvature Scale Space, where the x-axis is the normalised arc-length of the curve and the y-axis is the evolution parameter, specifically, the parameter of the filter applied. The plots on the graph form loops characteristic of the outline. Each convex or concave part of the object outline corresponds to a loop in the CSS image. The co-ordinates of the peaks of the most prominent loops in the CSS image are used as a representation of the outline.
To search for objects in images stored in a database matching the shape of an input object, the CSS representation of an input shape is calculated. The similarity between an input shape and stored shapes is determined by comparing the position and height of the peaks in the respective CSS images using a matching algorithm.
It is also known from the first-mentioned paper above to use two additional parameters, circularity and eccentricity of the original shape, to reject from the matching process shapes with significantly different circularity and eccentricity parameters.
A problem with the representation as described above is that retrieval accuracy is sometimes poor, especially for curves which have a small number of concavities or convexities. In particular, the representation cannot distinguish between various convex curves.
An aspect of the present invention is to introduce an additional means of describing the shape of the “prototype contour shape”. The prototype contour shape is defined here preferably as:
1) The original shape if there are no convexities or concavities in the contour (i.e. there are no peaks in the CSS image), or
2) The contour of the shape after smoothing equivalent to the highest peak in the CSS image.
Note, that the prototype contour shape is always convex.
For example, the shape of the prototype contour can be described by means of the invariants based on region moments as described in the paper “Visual Pattern Recognition by Moments Invariants”, IEEE Transaction on Information Theory, Vol. IT-8, 179-187, 1962 by M. K. Hu the contents of which are incorporated herein by reference or using the Fourier descriptors as described in the paper “On Image Analysis by the Methods of Moments”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 10, No. 4, July 1988, by Cho-Huak The, the contents of which are incorporated herein by reference, or parameters such as eccentricity, circularity, etc. In the known method mentioned above, eccentricity and circularity is only used in relation to the original shape. Here we use it in relation to a “prototype shape”, which is different for curves which have at least one CSS peak. Another difference is that in the known method eccentricity and circularity are used to reject certain shapes from the similarity matching, and here we use them (in addition to CSS peaks) to derive the value of the similarity measure. Finally, we extend the additional parameters used in the matching process to the moment invariants, Fourier descriptors and Zernike Moments.
As a result of the invention, the retrieval accuracy can be improved.